<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            时间：O(N^2)
            空间：O(N)
        */
        function TreeNode(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        var constructFromPrePost = function (preorder, postorder) {
            // 退出条件
            if (preorder.length === 0) {
                return null
            }

            // 只有一个元素
            if (preorder.length === 1) {
                return new TreeNode(preorder[0])
            }

            // 前序数组第一个元素拿来
            let value1 = preorder[1]
            let deli;
            for (deli = 0; deli < postorder.length; deli++) {
                // 在中序中找到这个元素
                if (postorder[deli] === value1) {
                    break
                }
            }
            // 头结点是preorder的第一个元素
            let root = new TreeNode(preorder[0])

            /* 
                前序是[1,2,4,5,3,6,7] 索引0是头结点值，索引1拿来分割;切割为[2,4,5]和[3,6,7]
                后序是[4,5,2,6,7,3,1], 切割为[4, 5, 2] 和 [6, 7, 3]

            */
            const leftSize = deli + 1
            const leftPreorder = preorder.slice(1, leftSize + 1)
            const leftPostorder = postorder.slice(0, leftSize)

            const rightPreorder = preorder.slice(leftSize + 1)
            const rightPostorder = postorder.slice(leftSize, postorder.length - 1) // 最后一个是根元素，不要了

            root.left = constructFromPrePost(leftPreorder, leftPostorder)
            root.right = constructFromPrePost(rightPreorder, rightPostorder)
            // 返回内容
            return root
        };
        console.log(constructFromPrePost([1,2,4,5,3,6,7], [4,5,2,6,7,3,1]));
        // console.log(constructFromPrePost([2, 3, 6, 8, 9, 5], [6, 3, 8, 9, 2, 5]));

        /* 
        
            对比：
                中序与后序，左中右 和 中右左，拿postorder的最后0个元素去切割inorder，因为后序的最后一个一定是根节点
                前序和中序，中左右 和 左中右，拿preorder的第0个元素去切割inorder，因为前序的第一个一定是根节点
                前序和后序，中左右 和 左右中，答案不唯一，我们规定前序的第0个是根节点，第一个是切割元素，去切割中序，左边的包括这个切割的都是左子树，右边的都是右子树
        */
    </script>
</body>

</html>